package sort;

/**
 * @author czt
 * @version 1.0
 * @since 2025/1/8
 * 堆排序
 */
public class Heap {

    /**
     * 1.建立大顶堆
     * 2.每次将堆顶元素交换到末尾，调整堆顶元素，让他重新符合大顶堆的特性
     */
    public int[] HeapSort(int[] arr) {
        heapify(arr,arr.length);
        for (int right = arr.length - 1; right > 0; right--) {
            swap(arr, 0, right);
            down(arr, 0, right);
        }
        return arr;
    }

    private static void heapify(int[] arr, int size) {
        for (int i = size >> 2 - 1; i >=0; i--) {
            down(arr, i, size);
        }
    }

    // 下潜
    private static void down(int[] array, int parent, int size) {
        while (true) {
            int left = parent * 2 + 1;
            int right = left + 1;

            int max = parent;
            if (left < size && array[left] > array[max]) {
                max = left;
            }

            if (right < size && array[right] > array[max]) {
                max = right;
            }
            if (max == parent) { // 没有更大的孩子
                // 退出循环
                break;
            }  // 找到了更大的孩子
            swap(array, max, parent);
            parent = max;
        }
    }

    private static void swap(int[] array, int i, int j) {
        int t = array[i];
        array[i] = array[j];
        array[j] = t;
    }
}
